{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Subarrays With GCD Equal to K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarrayGCD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大公因数等于 K 的子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code> ，请你统计并返回 <code>nums</code>&nbsp;的子数组中元素的最大公因数等于 <code>k</code>&nbsp;的子数组数目。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中一个连续的非空序列。</p>\n",
    "\n",
    "<p><strong>数组的最大公因数</strong>&nbsp;是能整除数组中所有元素的最大整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [9,3,1,2,6,3], k = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>nums 的子数组中，以 3 作为最大公因数的子数组如下：\n",
    "- [9,<strong><em>3</em></strong>,1,2,6,3]\n",
    "- [9,3,1,2,6,<em><strong>3</strong></em>]\n",
    "- [<strong><em>9,3</em></strong>,1,2,6,3]\n",
    "- [9,3,1,2,<em><strong>6,3</strong></em>]\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [4], k = 7\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不存在以 7 作为最大公因数的子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-subarrays-with-gcd-equal-to-k](https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-subarrays-with-gcd-equal-to-k](https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,3,1,2,6,3]\\n3', '[4]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            g = 0\n",
    "\n",
    "            for j in range(i, len(nums)):\n",
    "\n",
    "                g = gcd(g, nums[j])\n",
    "\n",
    "                if g % k: break\n",
    "\n",
    "                if g == k: ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k: ans += 1\n",
    "                elif g < k: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k: ans += 1\n",
    "                elif g % k: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(nums[j], g)\n",
    "                if g % k:\n",
    "                    break\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []  # [GCD，相同 GCD 区间的右端点]\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k:  # 保证后续求的 GCD 都是 k 的倍数\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x, i])\n",
    "            # 原地去重，因为相同的 GCD 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:  # a[0][0] >= k\n",
    "                ans += a[0][1] - i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        # on2\n",
    "        from math import gcd \n",
    "        n=len(nums)\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            x=nums[i]\n",
    "            for j in range(i,n):\n",
    "                x=gcd(x,nums[j])\n",
    "                if x==k:\n",
    "                    cnt+=1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if nums[j] // g == 0: break\n",
    "                if g == k: ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        left, n = 0, len(nums)\n",
    "        GCD, end = [], n\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            if num % k != 0:\n",
    "                GCD = []\n",
    "                end = i\n",
    "                continue\n",
    "\n",
    "            GCD.append([num, i])\n",
    "            j = 0\n",
    "            for g in GCD:\n",
    "                g[0] = gcd(num, g[0])\n",
    "                if g[0] == GCD[j][0]:\n",
    "                    GCD[j][1] = g[1]\n",
    "                else:\n",
    "                    j += 1\n",
    "                    GCD[j] = [g[0], g[1]]\n",
    "            del GCD[j+1:]\n",
    "            if GCD[0][0] == k:\n",
    "                ans += end - GCD[0][1]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = gcd(g,nums[j])\n",
    "                if g % k:\n",
    "                   break\n",
    "                if g == k:\n",
    "                    ans += 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k != 0: break\n",
    "                if g == k: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % k != 0:\n",
    "                continue\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res +=1\n",
    "                if g < k:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            gg = nums[i]\n",
    "            for r in range(i, n):\n",
    "                gg = gcd(gg, nums[r])\n",
    "                if gg == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        # 小暴力\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for n in accumulate(nums[i:], gcd):\n",
    "                if n == k:\n",
    "                    ans += 1\n",
    "                elif n % k:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        ans = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            local = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                local = gcd(local, nums[j])\n",
    "                if local % k: break\n",
    "                if local == k:\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力枚举\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for x in nums[i:]:\n",
    "                g = gcd(g, x)\n",
    "                if g % k:\n",
    "                    break\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "    def gcd(a: int, b: int) -> int:\n",
    "        while a:\n",
    "            a, b = b % a, a\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        return sum(Counter(accumulate(nums[i:], gcd))[k] for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % k != 0:\n",
    "                continue\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % k != 0:\n",
    "                continue\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res +=1\n",
    "                if g % k != 0:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(n):\r\n",
    "            gcd = nums[i]\r\n",
    "            for j in range(i, n):\r\n",
    "                gcd = math.gcd(gcd, nums[j])\r\n",
    "                if gcd == k:\r\n",
    "                    ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % k != 0:\n",
    "                continue\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        left, ans = -1, 0        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k == 0:               \n",
    "                while i > left and gcd(x, nums[i]) != k:\n",
    "                    i -= 1\n",
    "                ans += i - left                \n",
    "            else: left = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        \n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            g = nums[i]\n",
    "            if g == k:\n",
    "                ret += 1\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(x,y):\n",
    "            return y if x%y==0 else gcd(y,x%y)\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            now=nums[i]\n",
    "            for j in range(i,n):\n",
    "                now=gcd(now,nums[j])\n",
    "                if now==k:\n",
    "                    res+=1\n",
    "                elif now<k:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        \n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            current_gcd = nums[i]\n",
    "            for j in range(i, n):\n",
    "                current_gcd = gcd(current_gcd, nums[j])\n",
    "                if current_gcd == k:\n",
    "                    count += 1\n",
    "                # 当最大公因数变为小于 k 时，可以跳出内部循环\n",
    "                if current_gcd < k:\n",
    "                    break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            val = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                val = gcd(val, nums[j])\n",
    "                if val % k != 0:\n",
    "                    break\n",
    "                if val == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "            最大公因数  \n",
    "            利用 \n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        a =[]\n",
    "        i0 =-1\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            if x%k:\n",
    "                a=[]\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x,i])\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0],x)\n",
    "                if a[j][0]!=p[0]:\n",
    "                    j+=1\n",
    "                    a[j]=p\n",
    "                else:\n",
    "                    a[j][1]=p[1]\n",
    "            del a[j+1:]\n",
    "            if a[0][0]==k:\n",
    "                ans += a[0][1]-i0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g < k:\n",
    "                    break\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            GCD=0\n",
    "            for j in range(i,n):\n",
    "                GCD=gcd(GCD,nums[j])\n",
    "                if GCD<k: break\n",
    "                elif GCD==k:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k:\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x, i])\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:\n",
    "                ans += a[0][1] - i0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i , n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        import math\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            gcd = 0\n",
    "            for j in range(i,len(nums)):\n",
    "                gcd = math.gcd(gcd,nums[j])\n",
    "                if gcd%k != 0:\n",
    "                    break\n",
    "                if gcd == k:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        gcd(a,b)=gcd(a,a+b)=gcd(a,k⋅a+b)\n",
    "        gcd(ka,kb)=k⋅gcd(a,b)。\n",
    "        多个整数的最大公约数：gcd(a,b,c)=gcd(gcd(a,b),c)。\n",
    "        若 gcd(a,b)=d，则 gcd(a/d,b/d)=1，即 a/d=与 b/d=互素\n",
    "        gcd(a+cb,b)=gcd(a,b)\n",
    "    '''\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        # 小暴力\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for n in accumulate(nums[i:], gcd):\n",
    "                if n == k:\n",
    "                    ans += 1\n",
    "                elif n < k:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 暴力枚举\n",
    "    # https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/solutions/1917454/by-endlesscheng-1f1r/\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k:\n",
    "                    break\n",
    "\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if i == j:\n",
    "                    GCD = nums[i]\n",
    "                else:\n",
    "                    GCD = gcd(GCD, nums[j])\n",
    "                # print(GCD)\n",
    "                if GCD == k:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 用GCD的性质。枚举右端点求左端点过程，需要向前遍历求gcd，gcd一定是所求数的因子，而每个数的因子个数不超过logU，因为因子至少为2，则相对的另一个因子至少为原数减半，所以数的因子个数不超过logU个。并且向前累计求gcd过程中要么不变，要么变小，也即相同的gcd会位于相邻位置，所以可以合并这些相同gcd的下标，也即向前枚举过程不同gcd的数目不超过logU个，则遍历右端点过程，对前面下标求gcd时，个数不会超过logU，并合并相同的gcd，相当于合并非递减数组，可以做到O(n)时间原地合并，此处的数组长度n为logU，而每次求gcd时间不会超过logU，所以遍历每个下标作为右端点时的时间复杂度为O((logU) ^ 2)，共O(n)个下标，所以总时间为O(n * (logU) ^ 2)，甚至可以求解n = 1e5范围\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k:\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([i, x])\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[1] = gcd(p[1], x)\n",
    "                if p[1] != a[j][1]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][0] = p[0]\n",
    "            a = a[:j + 1]\n",
    "            if a[0][1] == k:\n",
    "                ans += a[0][0] - i0\n",
    "        return ans\n",
    "\n",
    "    def gcd(a: int,  b: int) -> int:\n",
    "        while a:\n",
    "            a, b = b % a, a\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 暴力枚举\n",
    "    # O(n(n+logU)) O(1)\n",
    "    # https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/solutions/1917454/by-endlesscheng-1f1r/\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k:\n",
    "                    break\n",
    "\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "    # 利用 GCD 的性质\n",
    "    # O(nlogU) O(log⁡U)\n",
    "    # https://leetcode.cn/link/?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV1ne4y1e7nu\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []  # [GCD，相同 GCD 区间的右端点]\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k:  # 保证后续求的 GCD 都是 k 的倍数\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "\n",
    "            a.append([x, i])\n",
    "            # 原地去重，因为相同的 GCD 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                # p是reference p在a中的值会被修改\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:  # a[0][0] >= k\n",
    "                ans += a[0][1] - i0\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        a=[]\n",
    "        ans=0\n",
    "        i0=-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x%k:\n",
    "                a=[]\n",
    "                i0=i\n",
    "                continue\n",
    "            a.append([x,i])\n",
    "            j=0\n",
    "            for p in a:\n",
    "                p[0]=gcd(p[0],x)\n",
    "                if a[j][0]!=p[0]:\n",
    "                    j += 1\n",
    "                    a[j]=p\n",
    "                else:\n",
    "                    a[j][1]=p[1]\n",
    "            del a[j+1:]\n",
    "            if a[0][0]==k:\n",
    "                ans += a[0][1]-i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k: break\n",
    "                if g == k: ans += 1\n",
    "        return ans\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            GCD=0\n",
    "            for j in range(i,n):\n",
    "                GCD=gcd(GCD,nums[j])\n",
    "                if GCD==k:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                \n",
    "                if g == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            g = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g % k != 0:\n",
    "                    break\n",
    "                if g == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res += 1\n",
    "                elif g < k:\n",
    "                    break\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            x = 0\n",
    "            for j in range(i, n):\n",
    "                x = gcd(nums[j], x)\n",
    "                if x % k != 0:\n",
    "                    break\n",
    "                if x == k:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 用GCD的性质。枚举右端点求左端点过程，需要向前遍历求gcd，gcd一定是所求数的因子，而每个数的因子个数不超过logU，因为因子至少为2，则相对的另一个因子至少为原数减半，所以数的因子个数不超过logU个。并且向前累计求gcd过程中要么不变，要么变小，也即相同的gcd会位于相邻位置，所以可以合并这些相同gcd的下标，也即向前枚举过程不同gcd的数目不超过logU个，则遍历右端点过程，对前面下标求gcd时，个数不会超过logU，并合并相同的gcd，相当于合并非递减数组，可以做到O(n)时间原地合并，此处的数组长度n为logU，而每次求gcd时间不会超过logU，所以遍历每个下标作为右端点时的时间复杂度为O((logU) ^ 2)，共O(n)个下标，所以总时间为O(n * (logU) ^ 2)，甚至可以求解n = 1e5范围\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % k:\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([i, x])\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[1] = gcd(p[1], x)\n",
    "                if p[1] != a[j][1]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][0] = p[0]\n",
    "            del a[j + 1:]\n",
    "            if a[0][1] == k:\n",
    "                ans += a[0][0] - i0\n",
    "        return ans\n",
    "\n",
    "    def gcd(a: int,  b: int) -> int:\n",
    "        while a:\n",
    "            a, b = b % a, a\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == k:\n",
    "                    res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayGCD(self, nums: List[int], k: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        ans = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            local = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                local = gcd(local, nums[j])\n",
    "                if local == k:\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
